#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <valarray>
#include <sstream>

using namespace std;

//92. 递归实现指数型枚举
//https://www.acwing.com/problem/content/94/

/*
const int N = 16;
int st[N];//状态，记录每个位置当前的状态：0表示未考虑，1表示选，2表示不选
int n;

void dfs(int u){
    //到枚举边界则开始输出
    if (u > n){
        //从头遍历每一位看是否选择
        for (int i = 1; i <= n; ++i) {
            if (st[i] == 1)
                printf("%d ",i);
        }
        printf("\n");
        return;
    }

    st[u] = 2;//不选
    dfs(u + 1);//递归到下一位
    st[u] = 0;//恢复变之前的状态

    st[u] = 1;//选
    dfs(u + 1);
    st[u] = 0;//恢复状态
}

int main() {
    //cin >> n;
    n = 3;
    dfs(1);//传入当前枚举的第几位
    return 0;
}
*/

/*
const int N = 16;

int n;
int st[N];
int ways[1 << 15][16], cnt;

void dfs(int u){
    if (u > n){
        for (int i = 1; i <= n; ++i) {
            if (st[i] == 1)
                ways[cnt][i] = i;
        }
        ++cnt;
        return;
    }

    st[u] = 2;
    dfs(u + 1);
    st[u] = 0;

    st[u] = 1;
    dfs(u + 1);
    st[u] = 0;
}

int main(){
    //cin >> n;
    n = 3;
    dfs(1);
    for (int i = 0; i < cnt; ++i) {
        for (int j = 1; j <= n; ++j) {
            printf("%d ",ways[i][j]);
        }
        puts("");
    }
    return 0;
}
*/

/*
const int N = 16;

int n;
int st[N];
vector<vector<int>> ways;

void dfs(int u){
    if (u > n){
        vector<int> way;
        for (int i = 1; i <= n; ++i) {
            if (st[i] == 1)
                way.push_back(i);
        }
        ways.push_back(way);
        return;
    }

    st[u] = 2;
    dfs(u + 1);
    st[u] = 0;

    st[u] = 1;
    dfs(u + 1);
    st[u] = 0;
}

int main(){
    //cin >> n;
    n = 3;
    dfs(1);
    for (auto& way : ways) {
        for (int j : way) {
            printf("%d ",j);
        }
        puts("");
    }
    return 0;
}
*/


//94. 递归实现排列型枚举
//https://www.acwing.com/problem/content/96/

/*
const int N = 10;
int n;
int state[N];//0表示还没放数，1~n表示放了对应的数
bool used[N];//true表示用过，false表示没用过

void dfs(int u){
    if (u > n){
        for (int i = 1; i <= n ; ++i) {
            printf("%d ",state[i]);
        }
        puts("");
        return;
    }

    for (int i = 1; i <= n; ++i) {
        if (!used[i]){
            state[u] = i;
            used[i] = true;
            dfs(u + 1);

            //恢复现场
            state[u] = 0;
            used[i] = false;
        }
    }
}

int main(){
    //cin >> n;
    n = 3;
    dfs(1);
    return 0;
}
*/

//93. 递归实现组合型枚举
//https://www.acwing.com/problem/content/95/

const int N = 30;
int n, m;
int way[N];//dfs过程中要存放的三个位置

//dfs的参数：
//当前该枚举哪个位置 u
//当前最小可以从哪个数开始枚举 start
void dfs(int u, int start){
    //优化部分：已经选择的（u-1）加上剩余能选的（n-start+1），不足m个，则退出
    if (u + n - start < m)
        return;
    //停止条件
    if (u == m+1){
        for (int i = 1; i <= m; ++i) {
            printf("%d ",way[i]);
        }
        puts("");
        return;
    }

    for (int i = start; i <= n; ++i) {
            way[u] = i;
            dfs(u + 1, i + 1);
            way[u] = 0;
        }
    }

int main(){
    n = 5,m = 3;
    dfs(1,1);
    return 0;
}

//带分数
//带分数中数字1~9分别出现且只出现一次，输出表示的全部种数

/*
const int N = 10;

int target;//目标数
int num[N];//保存全排列的结果
bool used[N];//全排列过程中是否使用过
int Count;

//计算对应的数字大小
int calc(int start, int end){
    int res = 0;
    for (int i = start; i <= end; ++i) {
        res = res * 10 + num[i];
    }
    return res;
}

//生成全排列
void dfs(int u){
    //全排列生成后进行分段
    //两层循环生成三段
    if (u == 9){
        for (int i = 0; i < 7; ++i) {
            for (int j = i+1; j < 8; ++j) {
                int a = calc(0,i);
                int b = calc(i + 1, j);
                int c = calc(j + 1,8);
                if (a * c + b == c * target)
                    ++Count;
            }
        }
        return;
    }

    for (int i = 1; i <= 9; ++i) {
        if (!used[i]){
            used[i] = true;
            num[u] = i;
            dfs(u + 1);

            used[i] = false;
        }
    }
}

int main(){
    scanf("%d",&target);
    dfs(0);
    printf("%d\n",Count);
    return 0;
}
*/

/*
const int N = 20;
int n;
bool st[N], backup[N];
int ans;

bool check(int a, int c){
    //求b
    int b = n * c - a * c;
    //判断a,b,c为0
    if (!a || !b || !c)
        return false;

    memcpy(backup,st,sizeof st);

    //判断b的每一位数字是否与a,c重复
    while (b){
        int x = b % 10;
        b /= 10;
        if (!x || backup[x])
            return false;
        backup[x] = true;
    }

    //判断1~9是否都被使用
    for (int i = 1; i <= 9; ++i) {
        if (!backup[i])
            return false;
    }

    return true;
}

void dfs_c(int u, int a, int c){
    if (u == n)
        return;
    if (check(a,c))
        ++ans;
    for (int i = 1; i <= 9; ++i) {
        if (!st[i]){
            st[i] = true;
            dfs_c(u + 1, a, c * 10 + i);
            st[i] = false;
        }
    }
}

void dfs_a(int u, int a){
    if (a >= n)
        return;
    if (a)
        dfs_c(u,a,0);
    for (int i = 1; i <= 9; ++i) {
        if (!st[i]){
            st[i] = true;
            dfs_a(u + 1, a * 10 + i);
            st[i] = false;
        }
    }
}

int main(){
    cin >> n;
    dfs_a(0,0);
    cout << ans << endl;
    return 0;
}
 */

//斐波那契数列
//递推

/*
int main(){
    int n;
    cin >> n;
    int f[50];
    f[1] = 0, f[2] = 1;
    for (int i = 3; i <= n; ++i) {
        f[i] = f[i - 1] + f[i - 2];
    }
    for (int i = 1; i <= n; ++i) {
        cout << f[i] << ' ';
    }
    return 0;
}
*/

/*
int main(){
    int n;
    cin >> n;
    int a = 0, b = 1;
    for (int i = 0; i < n; ++i) {
        cout << a << ' ';
        int fn = a + b;
        a = b;
        b = fn;
    }
    return 0;
}
*/

//翻硬币

/*
const int N = 101;
size_t n;
char start[N],aim[N];

void turn(int i){
    if (start[i] == '*')
        start[i] = 'o';
    else
        start[i] = '*';
}

int main(){
    cin >> start >> aim;
    n = strlen(start);
    int res = 0;
    for (int i = 0; i < n - 1; ++i) {
        if (start[i] != aim[i]){
            turn(i), turn(i + 1);
            ++res;
        }
    }
    cout << res << endl;
    return 0;
}
*/

//飞行员兄弟

/*
typedef pair<int, int> PII;

const int N = 5;
char g[N][N], backup[N][N];

int get(int x, int y){
    return x*4 + y;
}

void turn_one(int x, int y){
    if (g[x][y] == '+')
        g[x][y] = '-';
    else
        g[x][y] = '+';
}

void turn_all(int x, int y){
    for (int i = 0; i < 4; ++i) {
        turn_one(x,i);
        turn_one(i,y);
    }
    turn_one(x,y);
}

int main(){
    for (int i = 0; i < 4; ++i) {
        cin >> g[i];
    }
    vector<PII> res;
    for (int op = 0; op < 1 << 16; ++op) {

        vector<PII> temp;

        //备份
        memcpy(backup,g,sizeof g);

        for (int i = 0; i < 4; ++i) {
            for (int j = 0; j < 4; ++j) {
                if (op >> get(i,j) & 1){
                    temp.push_back({i,j});
                    turn_all(i,j);
                }
            }
        }

        //判断是否全亮
        bool has_closed = false;
        for (int i = 0; i < 4; ++i) {
            for (int j = 0; j < 4; ++j) {
                if (g[i][j] == '+')
                    has_closed = true;
            }
        }
        if (!has_closed)
            if (res.empty() || res.size() > temp.size())
                res = temp;

        //还原初始状态
        memcpy(g,backup,sizeof g);
    }
    cout << res.size() << endl;
    for (auto pc : res) {
        cout << pc.first+1 << ' ' << pc.second+1 << endl;
    }
    return 0;
}
*/

//数的范围

/*
const int N = 100010;
int n, m;
int q[N];

int main(){
    scanf("%d%d",&n,&m);
    for (int i = 0; i < n; ++i) {
        scanf("%d",&q[i]);
    }
    for (int i = 0; i < m; ++i) {
        int x;
        scanf("%d",&x);

        //二分x的左端点
        int l = 0, r = n - 1;
        while (l < r){
            int mid = l + r >> 1;
            if (q[mid] >= x)
                r = mid;
            else
                l = mid + 1;
        }
        if (q[l] == x){
            cout << r << ' ';

            //二分x的右端点
            r = n - 1;//右端点一定在左端点到末尾之间
            while (l < r){
                int mid = l + r + 1 >> 1;//因为是l=mid,所以多加一
                if (q[mid] <= x)
                    l = mid;
                else
                    r = mid - 1;
            }
            cout << l << endl;
        } else
            cout << "-1 -1" << endl;
    }

    return 0;
}
*/

//数的三次方根

/*
int main(){
    double x;
    cin >> x;
    double l = -10000, r = 10000;
    while (r - l > 1e-8){
        double mid = (l + r) / 2;
        if (mid * mid * mid >= x)
            r = mid;
        else
            l = mid;
    }
    printf("%lf\n",l);
    return 0;
}
*/

//730. 机器人跳跃问题
//https://www.acwing.com/problem/content/732/

/*
const int N = 10010;
int n;
int h[N];

bool check(int e){
    for (int i = 0; i < n; ++i) {
        e = e * 2 - h[i];
        if (e >= 1e5)
            return true;
        if (e < 0)
            return false;
    }
    return true;
}

int main(){
    scanf("%d",&n);
    for (int i = 0; i < n; ++i) {
        scanf("%d",&h[i]);
    }
    int l = 0, r = 1e5;
    while (l < r){
        int mid = (l + r) / 2;
        if (check(mid))
            r = mid;
        else
            l = mid + 1;
    }
    printf("%d\n",l);
    return 0;
}
*/

//1221 四平方和

/*
const int N = 2500010;
int n;

int main(){
    cin >> n;
    for (int a = 0; a * a <= n; ++a) {
        for (int b = a; b * b + a * a <= n; ++b) {
            for (int c = b; c * c + b * b + a * a <= n; ++c) {
                int tmp = n - a * a - b * b - c * c;
                int d = sqrt(tmp);
                if (d * d == tmp){
                    printf("%d %d %d %d\n",a,b,c,d);
                    return 0;
                }
            }
        }
    }
}
*/

/*
const int N = 2500010;

struct Sum{
    int s,c,d;
    bool operator<(const Sum& t)const{
        if (s != t.s)
            return s < t.s;
        if (c != t.c)
            return c < t.c;
        return d < t.d;
    }
}sum[N];

int n,m;

int main(){
    cin >> n;
    for (int c = 0; c * c <= n; ++c) {
        for (int d = c; d * d + c * c <= n; ++d) {
            sum[m++] = {c * c + d * d,c,d};
        }
    }
    sort(sum,sum + m);
    for (int a = 0; a * a <= n; ++a) {
        for (int b = a; b * b + a * a <= n; ++b) {
            int temp = n - a * a - b * b;
            int l = 0, r = m - 1;
            while (l < r){
                int mid = l + r >> 1;
                if (sum[mid].s >= temp)
                    r = mid;
                else
                    l = mid + 1;
            }
            if (sum[l].s == temp){
                printf("%d %d %d %d\n",a,b,sum[l].c,sum[l].d);
                return 0;
            }
        }
    }
    return 0;
}
*/

//1227 分巧克力

/*
const int N = 100010;

int n, k;
int h[N], w[N];

bool check(int mid){
    int res = 0;
    for (int i = 0; i < n; ++i) {
        res += (h[i] / mid) * (w[i] / mid);
        if (res >= k)
            return true;
    }
    return false;
}

int main(){
    scanf("%d%d", &n, &k);
    for (int i = 0; i < n; ++i) {
        scanf("%d%d", &h[i], &w[i]);
    }
    int l = 0, r = 1e5;
    while (l < r){
        int mid = l + r + 1 >> 1;
        if (check(mid))
            l = mid;
        else
            r = mid - 1;
    }
    printf("%d\n",l);
    return 0;
}
*/

//前缀和

/*
const int N = 100010;

int n, m;
int a[N];//表示原数组
int s[N];//表示前缀和数组

int main(){
    scanf("%d%d",&n, &m);
    for (int i = 1; i <= n; ++i) {
        scanf("%d",&a[i]);
        s[i] = s[i - 1] + a[i];
    }
    while (m--){
        int l, r;
        scanf("%d%d",&l, &r);
        printf("%d\n",s[r] - s[l-1]);
    }
    return 0;
}
*/

//子矩阵的和

/*
const int N = 1010;
int n, m, q;
int a[N][N], s[N][N];

int main(){
    scanf("%d%d%d", &n, &m, &q);
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            scanf("%d",&a[i][j]);
            s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j];
        }
    }
    while (q--){
        int x1, y1, x2, y2;
        scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
        printf("%d\n",s[x2][y2] - s[x1-1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1]);
    }
    return 0;
}
*/

//99 激光炸弹

/*
const int N =100010;
int n,k;
//long long s[N],cnt[N];
long long cnt[N];

long long res;

int main()
{
    //cin >> n >> k;
    cnt[0] = 1;
    n = 5, k = 2;
    long long s[6] = {0,1,3,6,10,15};
    for(int i = 1; i <= n; i ++ ){
        res += cnt[s[i] % k];
        cnt[s[i] % k]++ ;
    }
    cout << res;
    return 0;
}
*/

/*
const int N =100010;
int n,k;
long long s[N],cnt[N];
long long res;

int main()
{
    cnt[0] = 1;
    cin >> n >> k;

    for(int i = 1; i <= n; i ++ ) {
        cin >> s[i];
        s[i] += s[i - 1];
    }
    for(int i = 1; i <= n; i ++ ){
        res += cnt[s[i] % k];
        cnt[s[i] % k]++ ;
    }
    cout << res;
    return 0;
}
*/

//n皇后问题
/*
const int N = 20;
int n;
char g[N][N];
bool col[N], dg[N], udg[N];

void dfs(int u){
    if (u == n){
        for (int i = 0; i < n; ++i) {
            puts(g[i]);
        }
        puts("");
        return;
    }
    for (int i = 0; i < n; ++i) {
        if (!col[i] && !dg[u + i] && !udg[i - u + n]){
            g[u][i] = 'Q';
            col[i] = dg[u + i] = udg[i - u + n] = true;
            dfs(u + 1);
            col[i] = dg[u + i] = udg[i - u + n] = false;
            g[u][i] = '.';
        }
    }
}

int main(){
    cin >> n;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            g[i][j] = '.';
        }
    }
    dfs(0);
    return 0;
}
*/

/*
const int N = 20;
int n;
char g[N][N];

bool check(int x, int y){
    for (int i = 1; i <= x; ++i) {
        if (g[i-1][y-1] == 'Q')
            return false;
        if (g[i-1][x+y-i-1] == 'Q')
            return false;
        if (g[i-1][i-x+y-1] == 'Q')
            return false;
    }
    return true;
}

void dfs(int row){
    if (row > n){
        for (int i = 0; i < n; ++i) {
            puts(g[i]);
        }
        puts("");
        return;
    }
    for (int i = 1; i <= n; ++i) {
        if (check(row, i)){
            g[row-1][i-1] = 'Q';
            dfs(row + 1);
            g[row-1][i-1] = '.';
        }
    }
}

int main(){
    cin >> n;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            g[i][j] = '.';
        }
    }
    dfs(1);
    return 0;
}
*/

/*
const int N = 20;
char g[N][N];
int n;
bool row[N], col[N], dg[N], udg[N];

void dfs(int x, int y, int s){
    if (y == n)
        y = 0, ++x;
    if (x == n){
        if (s == n){
            for (int i = 0; i < n; ++i) {
                puts(g[i]);
            }
            puts("");
        }
        return;
    }
    //不放皇后
    dfs(x,y + 1, s);

    //放皇后
    if (!row[x] && !col[y] && !dg[x + y] && !udg[n + y - x]){
        g[x][y] = 'Q';
        row[x] = col[y] = dg[x + y] = udg[n + y - x] = true;
        dfs(x, y + 1, s + 1);
        row[x] = col[y] = dg[x + y] = udg[n + y - x] = false;
        g[x][y] = '.';
    }
}

int main(){
    cin >> n;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            g[i][j] = '.';
        }
    }
    dfs(0,0,0);
    return 0;
}
*/

//走迷宫

/*
const int N = 110;

int n, m;
int g[N][N];
int d[N][N];
pair<int, int> q[N * N];

template<typename _Tp>
const valarray<_Tp> &bfs();

int bfs(){
    int hh = 0, tt = 0;
    q[0] = {0, 0};

    memset(d, -1, sizeof d);
    d[0][0] = 0;

    int dx[4] = {-1, 0, 1, 0};
    int dy[4] = {0, 1, 0, -1};

    while (hh <= tt){
        auto t = q[hh++];
        for (int i = 0; i < 4; ++i) {
            int x = t.first + dx[i], y = t.second + dy[i];
            if (x >= 0 && x < n && y >= 0 && y < m && g[x][y] == 0 && d[x][y] == -1){
                d[x][y] = d[t.first][t.second] + 1;
                q[++tt] = {x, y};
            }
        }
    }
    return d[n -1][m - 1];
}

int main(){
    cin >> n >> m;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            cin >> g[i][j];
        }
    }
    cout << bfs() << endl;
    return 0;
}
*/

//01背包问题

/*
const int N = 1010;
int n, m;
int v[N], w[N];//体积和权重
int f[N][N];

int main(){
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        cin >> v[i] >> w[i];
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j <= m; ++j) {
            f[i][j] = f[i-1][j];
            if (j >= v[i])
                f[i][j] = max(f[i][j], f[i-1][j-v[i]] + w[i]);
        }
    }
    cout << f[n][m] <<endl;
    return 0;
}
*/

//填空

int GetMonthDay(int year, int month){
    int monthArray[13] = {0,31,28,31,30,31,30,31,31,30,31,30,31};
    if (month == 2 && ((year % 4 == 0 && year % 100 != 0)) || (year % 400 == 0))
        return 29;
    else
        return monthArray[month];
}

bool isContain(int day){
/*    stringstream ss;
    ss << day;
    string str = ss.str();
    for (auto pc : str) {
        if (pc == '2')
            return true;
    }*/
    while (day > 0){
        if (day % 10 == 2)
            return true;
        day /= 10;
    }
    return false;
}

void test1(){
    int cnt = 0;
    for (int i = 1900; i <= 9999; ++i) {
        for (int j = 1; j <= 12; ++j) {
            for (int k = 1; k <= GetMonthDay(i,j); ++k) {
                if (isContain(i) || isContain(j) || isContain(k))
                    ++cnt;
            }
        }
    }
    cout << cnt << endl;
}

void test2(){
    int cnt = 0;
    int days[] = {0,31,28,31,30,31,30,31,31,30,31,30,31};
    for (int year = 1900; year <= 9999; ++year) {
        if (((year % 4 == 0 && year % 100 != 0)) || (year % 400 == 0))
            days[2] = 29;
        else
            days[2] = 28;
        for (int month = 1; month <= 12; ++month) {
            for (int day = 1; day <= days[month]; ++day) {
                if (isContain(year) || isContain(month) || isContain(day))
                    ++cnt;
            }
        }
    }
    cout << cnt << endl;
}

int count(int x){
    int cnt = 0;
    while (x > 0){
        cnt += x % 10;
        x /= 10;
    }
    return cnt;
}

void test3(){
    int ret = 0;
    int days[] = {0,31,28,31,30,31,30,31,31,30,31,30,31};
    for (int year = 2001; year <= 2021; ++year) {
        if ((year % 4 == 0 && year % 100 != 0) || year % 400 == 0)
            days[2] = 29;
        else
            days[2] = 28;
        for (int month = 1; month <= 12; ++month) {
            for (int day = 1; day <= days[month]; ++day) {
                int sum = 0;
                sum += count(year);
                sum += count(month);
                sum += count(day);
                if ((int) sqrt(sum) * (int) sqrt(sum) == sum)
                    ++ret;
             }
        }
    }
    cout << ret << endl;
}

void test4(){
    for (int s = 0; s <= 6; ++s) {
        for (int f = 0; f < 60; ++f) {
            for (int m = 0; m < 60; ++m) {
                //走1秒转的角度
                double dm = 360 / 60 * m;
                //走1分钟转的角度（包含秒针的加成）
                double df = 360 / 60 * f + dm / 60;
                //走1小时转的角度（包含分秒针的加成）
                double ds = 360 / 12 * s + df / 60 * 5;

                double a = abs(df - ds), b = abs(df - dm);
                //有可能是反角，所以取小的那个角
                a = min(a, 360 - a), b = min(b,360 - b);

                //浮点型比较是相差非常小即相等
                if (fabs(a - 2 * b) <= 1e-6)
                    cout << s << " " << f << " " << m << endl;
            }
        }
    }
}

/*
int main(){
    test4();
    return 0;
}
*/
